Numerous techniques have been proposed and patented for pattern or character recognition. Some examples are discussed in the following articles and patents.
IBM Tech. Discl. Bull., Vol. 18, No. 3, Aug. 1975, pp 681-686, "Decision Function Design Algorithm for Pattern Recognition", by King, Jr. et al. This article teaches technique and algorithm which identify a pattern of an incoming image on the basis of a one-dimensional array of numbers that represent features. Unlike the present invention, this technique is unable to recognize two-dimensional actual geometry of the image without first converting the two-dimensional array of pixels into one-dimensional array. A similar technique is described in another IBM Tech. Discl. Bull., Vol. 16, No. 1, June 1973, pp 97-99, "Sequential Pattern Recognition Machine", by Hopkins et al.
Canadian Patent No. 1,210,870 Sept. 2, 1986 (Pastor). This patent discloses a process to extract linear features, for example, in images of characters. The process also uses the convolution technique. However the distinction that characterises any particular convolution technique is the kernel(s) of the convolution(s). The kernels of the convolutions in the patent are very different from those used in the linearity analysis of the present invention. Some of the are specific points of difference are:
b 1. The kernels used in the linearity analysis of the present invention are function of angle multiplied by a function of radial distance. Those used in the Canadian Patent are functions of horizontal distance multiplied by functions of vertical distance. PA0 2. The kernels used in the linearity analysis of the present invention span the full image. The kernels used in the patent are only a few pixels long and one pixel wide. PA0 3. The kernels used in the linearity analysis of the present invention have functional dependence 1/r.sup.2 in one direction and sin(2.theta.) or cos(2.theta.) in the other direction. The kernel used in the patent have functional dependence abs(x.sub.max -x) in one direction and no functional dependence at all in the other direction. PA0 4. The linearity analysis of the present invention produces results that are independent of the size of the image that is analyzed. The patent requires prior knowledge of the sizes of images to be analyzed. PA0 5. The linearity analysis of the present invention produces features; specifically, it produces results specifying direction and distinctness of linear features. The patent produces modified images. PA0 6. The linearity analysis of the present invention produces numerical results. The patent produces binary results. PA0 1. The patent is applicable only to binary image, i.e. only those in which each pixel can have one of only two possible values, e.g. black/white, one/zero or true/false. PA0 2. The process of the patent does not produce a measure of the distinctness of a linear feature. PA0 3. The process of the patent is based only on relation PA0 4. The patent does not use convolution.
Canadian Patent No. 1,218,156 Feb. 17, 1987 (Pastor et al). This patent is for hardware to run the process disclosed by the preceeding patent and the same considerations are therefore applicable to it. Canadian Patent No. 1,089,988 Nov. 18, 1980 (Evans et al). The purpose of this process is primarily to encode image data in a compact form for storage and transmission. It does, however, have a side effect of producing information about length and orientation of linear feature in the image. The following are the differences between the patent and the linearity analysis of the present invention:
ships among near neighbour pixels, while the linearity analysis of the present invention produces a result for each point of interest based on the entire image. Therefore, the results of the two processes are very different. In particular, the patented process will be much more sensitive to noise.
In a typical digitized image, the image is represented by being divided into a (usually regular) disjoint and exhaustive array of cells, commonly known as "pixels". Each pixel is approximated as being uniform and is characterized by a single number, its "value", representing typically an average of the intensity of light in the part of the image covered by that pixel. The image is represented by the set of these values stored in a numerical memory device.
An example of the sort of linear features is the strokes that compose the image of an alphabetic character. A reliable methods of discernment of these strokes could lead to a great improvement in processes for the reading of printed text by machine.
Other processes call for the detection of linear features in an image derived by some arithmetic process from an image prepared as above. The presently proposed process is equally applicable to such a derived image. An example of such a derived image is the magnitude of the pixel-to-pixel variation of an image prepared as above. In the derived image, a linear feature corresponds to an edge. Such edge detection might, for example, be useful in guiding a robot's hand to embrace an object it is to move.
The known processes respond strongly to noise, i.e. imperfection of reproduction, which is very common in digitized images. Causes include the imperfect fit of an object's outlines to the pattern of pixels (digitizing noise), dust on the object or optical elements, and random electronic events. Cumbersome post-processing of the results from known processes is necessary to eliminate this noise and such processing tends also to negate the detection of the features the process seeks.
The prior art processes also tend to be specific to features in certain rather narrow size ranges and yield inaccurate indications of whether separated segments of the image with some common property are part of the same feature; that is, they lack a holistic perception of the image. For this reason, most prior art machine vision processes do not use any process for the detection of linear features, but rather analyze images by various sorts of shape analysis.
An example of the resulting limitations is that optical character reading machines have difficulty distinguishing between "S" and "5", and between "Z" and "2". Since they do not discern lines, or do so only crudely, they are unable to distinguish between smooth curves and corners. Instead, they attempt to distinguish these pairs on the basis of characteristics that do not in fact define the characters. This provision makes them strongly sensitive to variations in font and to imperfect print quality. Another example of the resulting limitations is that robot vision devices require that items be presented to them in controlled orientation.